package summary;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/5 12:14
 * https://leetcode.cn/problems/subarray-sum-equals-k/
 */
public class Title560 {

    public static int subarraySum2(int[] nums, int k) {
        //<前缀和，出现的次数>
        Map<Integer, Integer> hash = new HashMap<>();
        int sum = 0;
        int count = 0;
        hash.put(0, 1);
        for (int i = 1; i <= nums.length; i++) {
            //前缀和
            sum += nums[i - 1];
            if (hash.containsKey(sum - k)) {
                count += hash.get(sum - k);
            }
            //放入当前的前缀和（当前前缀和只能被后边的前缀和使用，所以放在代码的最后）
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 1};
        int k = 0;
        int i = subarraySum2(nums, k);
        System.out.println(i);
    }
}
